#include"avl.h"
#include"stdio.h"
#include"stdlib.h"

//初始化
void AVLCreate(AVLTree* t){
    t->root = NULL;
}

int AVLTreeGetNodeHeight(AVLTreeNode* node){
    if(node==NULL){
        return -1;//空树节点高度为-1
    }
    return node->height;   
}

void  updataAVLNodeHeight(AVLTreeNode* node){
    if(node==NULL){
        return ;
    }
    int leftHeight = AVLTreeGetNodeHeight(node->left);
    int rightHeight = AVLTreeGetNodeHeight(node->right);
    node->height =  (leftHeight>rightHeight ? leftHeight :rightHeight)+1;
}


int BalanceFactor(AVLTreeNode* node){
    if (node == NULL){
        return 0;
    } 
    return AVLTreeGetNodeHeight(node->left) - AVLTreeGetNodeHeight(node->right);
}

AVLTreeNode* rightRotate(AVLTreeNode* y){
    //这是由左子树过长导致的LL型
    //特点 ：失衡节点的平衡因子大于1，失衡节点的左子树的平衡节点大于0
    //失衡节点是N ，需要右旋他的左子树
    //                        
    //       N                   S(x)
    //      / \   r-rotate(N)   / \
    //     S   R  ==========>  L   N(y)
    //    / \                 /   / \
    //   L   M               A   M   R
    //  /
    // A 
    AVLTreeNode* x = y->left;//S
    AVLTreeNode* T2 = x->right;//M
    x->right = y;
    y->left = T2;
    updataAVLNodeHeight(y);
    updataAVLNodeHeight(x);
    //更新自底向上
    return x;
}


AVLTreeNode* leftRotate(AVLTreeNode* y){
    //这是由右子树过长导致的RR型
    //特点 ：失衡节点的平衡因子小于-1，失衡节点的左子树的平衡节点小于0
    //失衡节点是N ，需要左旋他的左子树
    //     N                       S(x)
    //    / \     l-rotate(N)     / \
    //   L   S    ==========>    N(y)R
    //      / \                 / \   \
    //     M   R               L   M   A 
    //          \
    //           A 
    AVLTreeNode* x = y->right;//S
    AVLTreeNode* T2 = x->left;//M
    x->left = y;
    y->right = T2;
    updataAVLNodeHeight(y);
    updataAVLNodeHeight(x);
    //更新自底向上
    return x;
}

/*
    现在讨论下LR
    LR形是由于失衡节点的左子树的右子树导致的
    //特点 ：失衡节点的平衡因子大于1，失衡节点的左子树的平衡节点小于0
    为什么要如下下图那样矫正？
    先要左旋 再右旋

    // clang-format off
    //  Left-Right Case
    //     |                   |
    //     C                   C                 |
    //    /   l-rotate(A)     /   r-rotate(C)    B
    //   A    ==========>    B    ==========>   / \
    //    \                 /                  A   C
    //     B               A
    // clang-format on

*/
/*
    现在讨论一下RL
    RL形是由失衡节点的右子树的左子树导致的
    //特点 ：失衡节点的平衡因子小于-1，失衡节点的左子树的平衡节点大于0
    // clang-format off
    //  Right-Left Case
    //   |                 |
    //   A                 A                     |
    //    \   r-rotate(C)   \     l-rotate(A)    B
    //     C  ==========>    B    ==========>   / \
    //    /                   \                A   C
    //   B                     C
    // clang-format on
*/

// 平衡节点
AVLTreeNode* balanceNode(AVLTreeNode* node){
    if (node == NULL) return NULL;
    updataAVLNodeHeight(node);
    if(BalanceFactor(node)>1 && BalanceFactor(node->left)>0){//处理LL型
        return rightRotate(node);
    }else if(BalanceFactor(node)<-1 && BalanceFactor(node->right)<0){//处理RR型
        return leftRotate(node);
    }else if(BalanceFactor(node)>1 && BalanceFactor(node->right)<0){//处理LR型
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }else if(BalanceFactor(node)<-1 && BalanceFactor(node->left)>0){//处理RL型
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }else{//没有失衡
        return node;
    }
}

AVLTreeNode* AVLinsertNode(AVLTree*t,AVLTreeNode* node,eleType value){
    if(node==NULL){
        AVLTreeNode* newNode = (AVLTreeNode*)malloc(sizeof(AVLTreeNode));
        newNode->val = value;
        newNode->height = 0;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    //先遍历要找到插入的位置
    if(value < node->val){
        node->left = AVLinsertNode(t,node->left,value);
    }else if(value > node->val){
        node->right = AVLinsertNode(t,node->right,value);
    }else if(value == node->val){
        return node;//不允许插入重复的值
    }else{//现在找到了要判断是不是失衡了
        return balanceNode(node);
    }   
}

void AVLInsetr(AVLTree*t, eleType value){
    t->root = AVLinsertNode(t,t->root,value);
}

void AVLInOrder(AVLTree*t,AVLTreeNode* node){
    if(node){
        AVLInOrder(t,node->left);
        printf("%d" ,node->val);
        AVLInOrder(t,node->right);
    }
}

void AVLInorderTraversal(AVLTree*t){
    AVLInOrder(t,t->root);
    printf("\n");
}


AVLTreeNode* AVLRemoveNode(AVLTree*t,AVLTreeNode* node,eleType value){
    if(node==NULL){
        return NULL;
    }
    if(value<node->val){
       node->left = AVLRemoveNode(t,node->left,value);
    }else if(value>node->val){
        node->right = AVLRemoveNode(t,node->right,value);
    }else{//找到了分四种情况
        if(node->left==NULL&&node->right==NULL){//叶子节点
            node->val = 0;
            free(node);
            node = NULL;
        }else if(node->left==NULL){//如果有右儿子，但是没有左儿子   
            AVLTreeNode* rightChild = node->right;
            free(node);
            node = rightChild;
        }else if(node->right==NULL){
            AVLTreeNode* leftChild = node->left;
            free(node);
            node = leftChild;
        }else{//左右儿子
            AVLTreeNode* replacement = node->right;
            while(replacement->left){
                replacement = replacement->left;
            }//找到该节点的右子树的最小值，就是右子树的最左边的
            node->val = replacement->val;
            node->right = AVLRemoveNode(t,node->right,replacement->val);//找到了并替换了，现在不是父节点没有儿子，再次递归删一次就好了
            free(replacement);
            replacement = NULL;
        }
    }
    //删除和二叉搜索树是一样的
    //现在就是判断是不是失衡的
   return balanceNode(node);
}

void AVLRemove(AVLTree*t,eleType value){
    t->root = AVLRemoveNode(t,t->root, value);
}

void AVLDestry(AVLTree* t){
    while(t->root){
        AVLRemove(t,t->root->val);
    }
}
